#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

ugly_list = [1]      # cache


class Solution:
    """
    @param n: An integer
    @return: the nth prime number as description.
    """

    # ugly_list = [1]      # cache


    def nthUglyNumber(self, n):
        # write your code here
        len_ugly = len(ugly_list)

        if len_ugly >= n:
            return ugly_list[n-1]

        cur_max_ugly = ugly_list[len_ugly-1]
        while len_ugly < n:
            cur_max_ugly = self.get_next(cur_max_ugly + 1)
            ugly_list.append(cur_max_ugly)
            len_ugly += 1

        return cur_max_ugly

    @staticmethod
    def get_next(base):
        while True:
            if Solution.is_ugly(base):
                return base
            else:
                base += 1

    @staticmethod
    def is_ugly(num):
        assert num >= 2
        # nlist = [2, 3, 5]
        # nlist = [4, 6, 8, 9, 10, 24, 25, 2, 3, 5]
        # nlist = [4, 8, 9, 10, 24, 25, 2, 3, 5]
        # nlist = [25, 24, 9, 4, 2, 3, 5]
        nlist = [4, 9, 25, 2, 3, 5]
        # while num % 2 == 0: num /= 2
        # while num % 3 == 0: num /= 3
        # while num % 5 == 0: num /= 5

        for divid in nlist:
            while num % divid == 0: num /= divid

        return num == 1

def main():
    from time import time
    print("start main")

    # begin = time()
    s = Solution()
    print(s.nthUglyNumber(41))
    print(ugly_list)

    # pass_t = time() - begin
    # print(pass_t)
    # print(s.nthUglyNumber(11))

if __name__ == "__main__":
    main()
